IJTCS | 分论坛日程：区块链技术

编者按

首届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）将于2020年8月17日-21日在线上举行，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办。  

本次大会的主题为“理论计算机科学领域的最新进展与焦点问题”。大会共设7个分论坛，分别对算法博弈论、区块链技术、多智能体强化学习、机器学习理论、量子计算、机器学习与形式化方法和算法与复杂性等领域进行深入探讨。同时，大会特别开设了青年博士论坛、女性学者论坛与本科生科研论坛，荟集海内外知名专家学者，聚焦理论计算机前沿问题。有关信息将持续更新，敬请关注！

本期带来“区块链技术”分论坛精彩介绍。

“区块链技术”介绍

区块链技术的核心是用去中心化的方式实现大规模分布式数据库，使互联网上无法互相信任的用户之间，不需要借助可信第三方就能进行对可靠性和最终性要求很高的交易。这项技术被认为是继互联网之后最具颠覆性的技术创新，正在给很多行业，如金融、电子商务、知识产权保护、医疗保险等等带来巨大机遇和变革。

区块链行业的高速发展给计算机科学的很多方向，如密码学、分布式计算、编程语言、博弈论、计算机网络、形式化验证等等提出了很多重要的研究问题。在这次会议中，我们着重关注理论计算及相关学科在区块链领域的研究，邀请了多位活跃在这一领域前沿的学者来介绍他们的工作。相信这样的交流会给不同学科的科研人员和区块链行业的从业者带来思想的碰撞，使与会者了解最新的科研动态，促进国内外区块链领域的交流和发展。

“区块链技术”分论坛主席

陈  婧

纽约州立大学石溪分校

“区块链技术”分论坛议程

“区块链技术”分论坛报告简介

Grigore Rosu

Formal Design, Implementation and Verification of Blockchain Languages

Abstract

The usual post-mortem approach to formal language semantics and verification, where the language is firstly implemented and used in production for many years before a need for formal semantics and verification tools naturally arises, simply does not work anymore. New blockchain languages or virtual machines are proposed at an alarming rate, followed by new versions of them every few weeks, together with programs (or smart contracts) in these languages that are responsible for financial transactions of potentially significant value. Formal analysis and verification tools are therefore needed immediately for such languages and virtual machines. We will present recent academic and commercial results in developing blockchain languages and virtual machines that come directly equipped with formal analysis and verification tools. The main idea is to generate all these automatically, correct-by-construction from a formal language specification.

Shai Halevi

Can a Blockchain Keep a Secret

Abstract

Blockchains are gaining traction and acceptance, not just for cryptocurrencies but increasingly as a general-purpose architecture for distributed computing. In this work we seek solutions that allow a blockchain to act as a trusted long-term repository of secret information: Our goal is to deposit a secret with the blockchain and specify how to use it (e.g., the conditions under which it is released), and have the blockchain keep this information secret and use it only in the requested manner (e.g., only release it once the conditions are met). This simple functionality would be an enabler for many powerful applications, including signing statements on behalf of the blockchain, using blockchain as the control plane for a storage system, performing decentralized program-obfuscation-as-a-service, and many more.

We present a scalable solution for implementing this functionality on a public proof-of-stake blockchain, in the presence of a mobile adversary controlling a small minority of the stake, using proactive secret sharing techniques. The main challenge is that, on the one hand, scalability requires that we use small committees to represent the entire stake, but, on the other hand, a mobile adversary may be able to corrupt the entire committee if it is small. For this reason, prior proactive secret sharing solutions are either non-scalable or insecure in our setting.

We solve this issue using "player replaceability", where the committee is anonymous until after it performs its actions, as in the Algorand blockchain. (Algorand uses player replaceability to defend against DDoS attacks.) Our main technical contribution is a system that allows sharing and re-sharing of secrets among the members of small dynamic committees, without knowing who they are until after they perform their actions. Our solution handles a fully mobile adversary corrupting less than 25% of the stake at any time, and is scalable in terms of both the number of parties on the blockchain and the number of time intervals.

Joint work with Fabrice Benhamouda, Craig Gentry, Sergey Gorbunov, Hugo Krawczyk, Chengyu Lin, Tal Rabin, and Leonid Reyzin.

欧  嵬

基于区块链的社区医疗管控系统

摘  要

针对现有医疗数据存在的互联互通标准化程度低、数据安全与隐私保护不到位、数据深度挖掘和分析不全面等问题，设计了一种基于区块链的社区医疗管控系统。采用Fabric框架，结合国密算法，在保证用户医疗信息隐私性的前提下，实现了医疗资源的多方创建、共享与追加更新。测试结果表明：在保证数据隐私的前提下，实现了用户医疗信息的智能分析、智能转诊与随访等功能，所有性能指标均符合当前区块链行业标准。与现有集中式医疗系统相比，该系统融合了疾病防控、综合监督、健康教育等信息系统，促进了各医疗卫生单位公共卫生信息的共享与业务协同，实现了社区公共卫生工作的在线监督、动态管理与科学决策。

Maurice Herlihy

Correctness Conditions for Cross-Chain Deals

Abstract

Modern distributed data management systems face a new challenge: how can autonomous, mutually-distrusting parties cooperate safely and effectively? Addressing this challenge brings up questions familiar from classical distributed systems: how to combine multiple steps into a single atomic action, how to recover from failures, and how to synchronize concurrent access to data. Nevertheless, each of these issues requires rethinking when participants are autonomous and potentially adversarial.

We propose the notion of a \emph{cross-chain deal}, a new way to structure complex distributed computations that manage assets in an adversarial setting. Deals are inspired by classical atomic transactions, but are necessarily different, in important ways, to accommodate the decentralized and untrusting nature of the exchange.

Joint work with Barbara Liskov and Liuba Shrira.

李毓浩

Recent Development for the Incentive Ratio in BitTorrent Resource Sharing Networks

Abstract

The booming sharing economy has a common challenge in its eventual success: how to motivate the participating agents to take truthful actions out of own interests. In the long history of economics, mechanism design has played an important role in the development of allocation and pricing rules for a large class of market problems, especially auctions. This has led to, in the Internet age, much work dealing with related issues to shape an algorithmic mechanism design paradigm. Sharing economies, however, distinguish from the algorithmic mechanism design paradigm dramatically. Agents share resources with each other for mutual benefit. No central planner such as the auctioneer would exist to design a protocol to maximize revenue nor social welfare. The more general pricing and allocation rule of market equilibrium is known not to be incentive compatible in that an agent may misreport its utility function to gain more in the changed market equilibrium. 

Our incentive study has focused on the well known BitTorrent network which has, arguably, been the first successful Internet-scale resource sharing system. It is based on a distributed protocol where agents make their own decisions based on local information, actions of their own neighbors. Early works have modeled its tit-for-tat strategy as a proportional response protocol, and shown that the dynamics of such a protocol converges to a market equilibrium. Those nice properties justify the success of the BitTorrent system in different aspects as a desired solution. Recent studies have further developed an array of truthfulness results of the proportional response protocol against agent deviations in the forms of the weight cheating and edge deleting. However, it is recently shown that the proportional response protocol is not truthful against the Sybil attack where an agent may split its resource among its different copies. In a peer-to-peer system, Sybil attacks are grave threats and subvert the security of networks. As a remedy for this untruthful property under the Sybil attack, the incentive of any agent has been shown to generate a limited gain for oneself to pursue such an attack under several special networks, such as trees, cliques, and cycles.

In this work, we prove a tight incentive ratio of two for any agent launching such an attack under general networks. Combined with past work of truthfulness results on agent deviations by weight cheating and edge deleting, we conclude a complete study on agent incentives in the BitTorrent network's resource sharing service, showing the robustness of the BitTorrent system against all those popular adversary attacks.

陈  钟

Security Analysis Techniques For Blockchain Smart Contracts

Abstract

This talk will address issues of security vulnerability discovery and exception analysis of smart contract. Some research achievements from our research lab includes three vulnerability discovery techniques with regard to different application scenarios and an exception diagnosis method were introduced.

陈炤桦

CycLedger: A Scalable and Secure Parallel Protocol for Distributed Ledger via Sharding

Abstract

Traditional public distributed ledgers have not been able to scale-out well and work efficiently. Sharding is deemed as a promising way to solve this problem. By partitioning all nodes into small committees and letting them work in parallel, we can significantly lower the amount of communication and computation, reduce the overhead on each node's storage, as well as enhance the throughput of the distributed ledger. Existing sharding-based protocols still suffer from several serious drawbacks. The first thing is that all non-faulty nodes must connect well with each other, which demands a huge number of communication channels in the network. Moreover, previous protocols have faced great loss in efficiency in the case where the honesty of each committee's leader is in question. At the same time, no explicit incentive is provided for nodes to actively participate in the protocol.

We present CycLedger, a scalable and secure parallel protocol for distributed ledger via sharding. Our protocol selects a leader and a partial set for each committee, who are in charge of maintaining intra-shard consensus and communicating with other committees, to reduce the amortized complexity of communication, computation, and storage on all nodes. We introduce a novel semi-commitment scheme between committees and a recovery procedure to prevent the system from crashing even when leaders of committees are malicious. To add incentive for the network, we use the concept of reputation, which measures each node's trusty computing power. As nodes with a higher reputation receive more rewards, there is an encouragement for nodes with strong computing ability to work honestly to gain reputation. In this way, we strike out a new path to establish scalability, security, and incentive for the sharding based distributed ledger.

张  韧

NC-Max: Breaking the Throughput Limit of Nakamoto Consensus

Abstract

First implemented in Bitcoin, Nakamoto Consensus (NC) is the most influential consensus protocol in cryptocurrencies despite all the alternative protocols designed afterward. Nevertheless, NC is trapped with a security-performance tradeoff, largely limiting the latter. In this paper, we propose NC-Max, a consensus protocol that breaks the throughput limit and enables the full utilization of the nodes' bandwidth in confirming transactions. In particular, after identifying the mechanism through which NC's security limits its performance, we decouple transaction synchronization from confirmation with a two-step mechanism, relieving the limits on the block size and the block interval. Further, we introduce an accurate dynamic difficulty adjustment mechanism to explore the real-time network condition and to adjust the protocol's throughput accordingly. We analyze the security of NC-Max, proving that it resists selfish mining and transaction withholding attacks better than NC does. Our performance evaluation shows that NC-Max not only fully exploits the nodes' bandwidth to confirm transactions, but also shortens the overall transaction confirmation latency by at least a factor of four compared to NC without compromising security. NC-Max is implemented in Nervos CKB, a public permissionless blockchain that has operated smoothly since Nov. 2019.

Alessandro Chiesa

An Overview of Recursive Proofs

Abstract

In this talk I will explain what does it mean to recurse a cryptographic proof, why it matters for blockchains, and what approaches are known to achieve this efficiently.

Matt Weinberg

A Mechanism Designer's View of Cryptocurrencies

Abstract

In this talk I'll overview the design of cryptocurrencies from a mechanism design perspective, and survey several formal barriers in designing incentive-compatible cryptocurrencies, covering topics such as the economics of mining, transaction fees vs. block rewards, and longest-chain proof-of-stake.

李家荪

Direct Evidence of Bitcoin Wash Trading

Abstract

Using data leaked by hackers from a major Bitcoin exchange, we find that more than 2% and up to 33% of all transactions are wash trades, a type of market manipulation in which traders clear their own limit orders to "cook" transaction records. Our finding provides direct evidence for the widely-suspected "fake volume" allegations against cryptocurrency exchanges, which are so far only backed by indirect inference in the literature. We further characterize wash trading using our unique trader-level data: While wash trades do not incur a significant impact on Bitcoin prices, they do increase the fees collected on transactions and thus the exchange's revenue. We hypothesize that the exchange insiders themselves engage in wash trading – not to manipulate price but to inflate apparent trading volume so as to look more attractive to deceived customers. We find consistent evidence from the involvement of wash trading perpetrators and exchange insiders previously exposed in another price manipulation. We further use our direct evidence to evaluate the indirect inference techniques proposed in the literature.

高承实

分布式密钥技术在区块链中的基础性作用

摘  要

非对称密码技术是构建区块链应用的基石，但传统的非对称密码技术无法有效实现对分布式和去中心化系统的支持。分布式密钥技术可以实现对分布式系统的原生支持，非对称密码的分布式实现也是推动区块链技术与应用治理的实质性突破。分布式密钥可以实现丰富的业务逻辑组合。

关于IJTCS

简介 → 国际理论计算机联合大会重磅登场

推荐 → 大会特邀报告（一）

推荐 → 大会特邀报告（二）

日程 → 分论坛：算法博弈论

IJTCS注册信息

本次大会已经正式面向公众开放注册！每位参与者可以选择免费注册以观看线上报告，或是支付一定费用以进一步和讲者就报告内容进行交流，深度参与大会的更多环节。

• 观看线上报告：免费

• 完全注册：
  

• （普通）$100 /￥700
  （学生）$50 /￥350*
  作为参会人参加全部会议，直接在线提问讨论并参与特设互动环节

注册截止：2020年8月15日23:59

点击 ↓↓↓二维码↓↓↓ 跳转注册页面：

*学生注册：网站上注册后需将学生证含有个人信息和学校信息的页拍照发送至[e-mail]，邮件主题格式为＂Student Registration + 姓名＂。

大会主席

John Hopcroft

中国科学院外籍院士、北京大学访问讲席教授

林惠民

中国科学院院士、中国科学院软件研究所专家

大会联合主席

邓小铁

北京大学教授

顾问委员会主席

高  文

中国工程院院士、北京大学教授

梅  宏

中国科学院院士、CCF理事长

张平文

中国科学院院士、CSIAM理事长、北京大学教授

组织单位

欢迎注册

大会网站：

https://econcs.pku.edu.cn/ijtcs2020/IJTCS2020.html

注册链接：

https://econcs.pku.edu.cn/ijtcs2020/Registration.htm

联系人

大会赞助、合作等信息，请联系：[e-mail]

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”转大会注册页面